import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(ch == '(' || ch == '[' || ch == '{'){
                stack.push(ch);
            }else{
                if(stack.empty()){
                    return false;
                }
                char top = stack.pop();
                if((top == '(' && ch == ')') || (top == '[' && ch == ']') || (top == '{' && ch == '}')){

                }else{
                    return false;
                }
            }
        }
        if(!stack.empty()){
            return false;
        }
        return true;
    }

    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < tokens.length; i++){

            if(tokens[i] == "+") {
                int num1 = stack.pop();
                int num2 = stack.pop();
                stack.push(num2 + num1);
            }else if(tokens[i] == "-") {
                int num1 = stack.pop();
                int num2 = stack.pop();
                stack.push(num2 - num1);
            }else if(tokens[i] == "*") {
                int num1 = stack.pop();
                int num2 = stack.pop();
                stack.push(num2 * num1);
            }else if(tokens[i] == "/"){
                int num1 = stack.pop();
                int num2 = stack.pop();
                stack.push(num2 / num1);
            }else{
                stack.push(Integer.parseInt(tokens[i]));
            }
        }
        return stack.peek();
    }
}

class MinStack {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    public MinStack() {

    }

    public void push(int val) {
        stack.push(val);
        if(minStack.empty()){
            minStack.push(val);
            return;
        }

        if(minStack.peek() <= val){
            minStack.push(minStack.peek());
        }else{
            minStack.push(val);
        }

    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}


class MyCircularQueue {

    int[] arr;
    int head;
    int rear;

    public MyCircularQueue(int k) {
        arr = new int[k + 1];
        head = 0;
        rear = 0;
    }

    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }

        arr[rear] = value;
        rear = (rear + 1) % arr.length;
        return true;
    }

    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }

        head = (head + 1) % arr.length;
        return true;
    }

    public int Front() {
        if(isEmpty()){
            return -1;
        }

        return arr[head];
    }

    public int Rear() {
        if(isEmpty()){
            return -1;
        }

        if(rear == 0){
            return arr[arr.length - 1];
        }

        return arr[rear - 1];
    }

    public boolean isEmpty() {
        return head == rear;
    }

    public boolean isFull() {
        if((rear + 1) % arr.length == head){
            return true;
        }

        return false;
    }
}